Combining Progressive Hedging with a Frank-Wolfe Method to Compute Lagrangian Dual Bounds in Stochastic Mixed-Integer Programming

摘要

We present a new primal-dual algorithm for computing the value of theLagrangian dual of a stochastic mixed-integer program (SMIP) formed by relaxingits nonanticipativity constraints. This dual is widely used in decompositionmethods for the solution of SMIPs. The algorithm relies on the well-knownprogressive hedging method, but unlike previous progressive hedging approachesfor SMIP, our algorithm can be shown to converge to the optimal Lagrangian dualvalue. The key improvement in the new algorithm is an inner loop of optimizedlinearization steps, similar to those taken in the classical Frank-Wolfemethod. Numerical results demonstrate that our new algorithm empiricallyoutperforms the standard implementation of progressive hedging for obtainingbounds in SMIP.